import java.util.ArrayList;
import java.util.Stack;

import AIColorUSAStates.Node;


public class LimitedDepthSearch {

	public enum BreakType
	{
		Cut,
		Found,
		NotFound
	}
	
	private static ArrayList<State> visitedStates = new ArrayList<State>();
	
	private static Stack<RiverNode> stack = new Stack<RiverNode>();
	
	public static RiverNode endNode;
	
	public static BreakType start(int limitDepth, State begin, State end, Problem p)
	{
		RiverNode rootNode = new RiverNode(null, begin, 0);		
		stack.add(rootNode);
		
		int depth = 0;
		
		while (depth < limitDepth && !stack.empty()) {
			RiverNode currentNode = stack.pop();
			if (!visitedStates.contains(currentNode.state)){
				visitedStates.add(currentNode.state);
				ArrayList<State> nextStates = (ArrayList<State>) Transport.getNextValidStates(p, currentNode.state);
				
				// Create New Nodes
				for (int i = 0; i < nextStates.size(); i++) {
					if (nextStates.get(i).equals(end))
					{
						endNode = new RiverNode(currentNode, nextStates.get(i), currentNode.depth + 1);
						return BreakType.Found;
					}
						
					RiverNode tmpNode = new RiverNode(currentNode, nextStates.get(i), currentNode.depth + 1);
					stack.add(tmpNode);
				}
			}
			
			depth = currentNode.depth + 1;
		}
		
		return stack.isEmpty() ? BreakType.NotFound :  BreakType.Cut;
	}
}
